package gold.gold01;

/**
 * 简单
 * 就还是塞到数组里看比较好
 * 这里找了先把一个指针移到中间, 然后把后半段反转, 然后比较前后两段的值是否相同
 */
public class S0206回文链表 {
    /**
     * 99, 87
     * 单向链表也是可以翻转的, 这是我之前没有想过的。不过这样修改掉了原链表, 合适吗。
     * 要不整个旋转过来, 那么就不用做奇偶的判断了。
     * 先扫一遍数长度?使用dequeue来做栈可以。O(1)空间复杂度怎么实现?
     */
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        int lenCount = 1;
        ListNode countNode = head;
        while(countNode.next != null){
            lenCount ++;
            countNode = countNode.next;
        }
        if(lenCount <= 3){
            if(lenCount == 2) return head.val == head.next.val;
            return head.val == head.next.next.val;
        }
        int midLen = lenCount / 2; // 半截长度, 3->1, 2->1


        ListNode node1 = head;
        ListNode node2 = head.next;
        head.next = null;
        ListNode node3 = null;
        while(--midLen > 0 && node2 != null){
            node3 = node2.next;
            node2.next = node1;
            node1 = node2;
            node2 = node3;
        }
        // node1 是前半段的起点, node2是后半段的起点(为奇的话需要抛弃第一个点)
        if(lenCount % 2 == 1) node3 = node3.next;
        midLen = lenCount / 2;
        boolean flag = true;
        while (--midLen >= 0){
            if(node1.val != node3.val){
                flag = false;
                break;
            }
            node1 = node1.next;
            node3 = node3.next;
        }
        return flag;
    }

    /**
     * 别人的, 这里用递归属性来找尾结点非常好
     */
    private ListNode frontPointer;

    public boolean isPalindrome2(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            // 妙, 这里第一次跳出来的时候, currentNode指向的是尾结点, 比较尾结点和头结点是否相等
            // 不相等false, 相等的话头结点移位, 跳到上一层, 在上一层中, currentNode又指向了倒数第二个结点
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }


    public static void main(String[] args) {
        int[] source = new int[]{0, 2, 2, 1};
        ListNode input = new ListNode(0);
        ListNode aba = input;
        for(int i: source){
            aba.next = new ListNode(i);
            aba = aba.next;
        }

        System.out.println(new S0206回文链表().isPalindrome(input.next));
    }
}
